Point and Permute
概要
Point and PermuteはGarbled Circuitにおけるevaluation time を削減するテクニックであり、特に大規模な回路を構成する場合には重要な要素となってくる。
基本的なGarbled CircuitではGarblerはゲートを構成する4つの暗号文をランダムに並べ替え、Evaluatorは4つの暗号文すべてを復号化しなければならない(1つの暗号文だけが正しく復号化される)。これはゲートの並び順がwire labelの真理値を漏らさないようにするためである。
仕組み
Point and Permuteのアイデアはwire labelにcolor bitと呼ばれるrondom bitを付与することから始まる。
以下の図のように各inputに対して青と赤のcolor bitを付与している。
以下の流れに従ってGarbled Tableを作成する
1.Assign color bits to the wire labels
2.A wire labels reveal its own color
3.Order the 4 ciphertexts for the canonically, by the color of keys.
https://scrapbox.io/files/66d111ce533e28001d2a59f1.png
例えばEvaluatorが暗号化されたタグA1, B1を取得し、対応するカラービットがそれぞれ青と赤であったとすると、Evaluatorは正しいラベルを得るために3番目の暗号文を直接復号することができる。
例:ANDゲートの計算
入力ワイヤー1のラベル: (0, E(0)) または (1, E(1))
入力ワイヤー2のラベル: (0, E(0)) または (1, E(1))
table:garbled table
x y z
0 0 E(E(0))
0 1 E(E(0))
1 0 E(E(0))
1 1 E(E(1))
評価者が(1, E(1))と(0, E(0))という入力ラベルをOTで受け取った場合、color bitの組み合わせ(10)から直接3行目を選択し、その行だけを復号する
通常のGarbled Circuitであれば以下の情報が必要であり、最悪の場合Garbled Tableの4つの組み合わせを全て試すことになる。
入力ワイヤー1のラベル:( E(0), E(1))
入力ワイヤー2のラベル: (E(0), E(1))
もしランダム予測オラクルがあれば、単純な1回限りの暗号化を使ってGarbled Circuitの暗号化を行うことができるらしい
どうせピンポイントで暗号化ー復号化するなら全てのパターンを暗号化しないでいいというアイデア?
https://scrapbox.io/files/66d11e8f49567b001d0b30e6.png
H= random oracle (in practice: 1 call to AES)
実用的なアプリケーションでは、固定鍵AESを使用してインスタンス化することができる。
Point-and-permuteスキームでは、Evaluatorの復号計算を以下のように4分の1に減らすことができる。
https://scrapbox.io/files/66d11eb07e3b62001ce93185.png